\section{Problema 1: Impresiones Ordenadas}

\subsection{Introducción}

Una imprenta cuenta con dos máquinas muy particulares en las cuales se realizan tareas de impresión a gran escala. Los trabajos realizados en estas máquinas pueden ser muy distintos entre sí y para realizar un trabajo en una de las máquinas hay que preparar la misma para ello. Esta preparación tiene un costo ya que hay que cargar las tintas correspondientes, cambiar los rodillos, etc. Más aun, el costo de preparar la máquina para realizar un determinado trabajo depende de cuál haya sido el último trabajo realizado en la máquina (ya que las tintas y rodillos pueden reutilizarse de un trabajo a otro o descartarse, dependiendo de qué tan distintos son los trabajos a realizar).

Todos los días la empresa debe realizar una serie de trabajos $t_{1}$ , . . . , $t_{n}$ y los mismos tienen que realizarse en el orden en que vienen dados, sin excepción. Cada trabajo puede asignarse a cualquiera de las dos máquinas disponibles, siempre que se respete el orden de producción dado. Afortunadamente, se conoce el costo de preparar una máquina para realizar el trabajo $t_{i}$ luego de haber realizado el trabajo $t_{j}$ , para cada par de trabajos $t_{i}$ y $t_{j}$ , con $j < i$. También se conoce el costo inicial de preparar una máquina para cada uno de los trabajos, es decir, el costo de preparación si el trabajo es el primero realizado en la máquina.

Nos piden implementar un algoritmo que encuentre el orden y la distribución de los trabajos entre las máquinas para que el costo del total de los trabajos sea el mínimo.

Por ejemplo, si tengo 3 trabajos tal que arrancar con el primero cuesta 2, arrancar con el segundo cuesta 4 pero poner el segundo después del primero cuesta 1 y arrancar con el tercero cuesta 3 mientras que poner el tercero después del 1ro o del 2do cuesta 5, entonces el resultado que minimiza los costos sería procesar el trabajo 1 y 2 en una máquina y el 3 en otra distinta.


\subsection{Desarrollo}

Para resolver este problema vamos a resolver sub-problemas relacionados. En particular, queremos averiguar cuál es el orden que genera el costo mínimo si una de las máquinas termina con el trabajo i y la otra con el trabajo j (con $j \neq i$ y $j, i \in [0..n]$). Para esto, utilizamos una matriz como la siguiente:

\begin{figure}[here]
	\centerline{\includegraphics[scale = 0.7]{ej1-1.png}}
	\caption{Matriz con los resultados de los sub-problemas. En cada casilla [i,j] tenemos el costo mínimo de los trabajos su una de las máquinas termina con el trabajo i y la otra con el trabajo j}
	\label{fig:matriz1}
\end{figure}

La matriz refleja en cada columna la cantidad de trabajos que voy a utilizar. Como los trabajos respetan un orden (si $i < j$ y $t_{i}$ y $t_{j}$ se realizan en la misma máquina entonces $t_{i}$ se realiza antes que $t_{j}$) si tengo k trabajos, puedo asegurar que una de las dos máquinas al menos va a terminar con el trabajo k. La otra fila, por lo tanto, reflejará en qué valor termina la otra máquina. Hay que tener en cuenta que si tengo k trabajos y una máquina termina con el trabajo k, la otra termina con un trabajo estrictamente menor que k. Por lo tanto, podemos afirmar que la matriz sólo va a completarse en los sectores representados por los colores amarillo y verde. La parte de la matriz que está coloreada con celeste no va a utilizarse.

Por otro lado, va a ser distinta la forma en que se complete la sección de la matriz señalada con el color amarillo que la diagonal, señalada con color verde. La razón es la siguiente: el costo de agregar un trabajo $i$ a la máquina 2 cuando la máquina 1 termina con un valor k tal que $k \leq i - 2$ es único. Como en el paso anterior tengo $i - 1$ elementos y sé que la máquina 1 termina con un numero inferior a $i - 1$ es estrictamente necesario que la máquina 2 termine con el elemento $i - 1$. Por lo tanto, el costo de agregarle a esa máquina el elemento $i$ se puede calcular fácilmente dado que se conoce el trabajo anterior que realiza la máquina a la que lo estoy agregando.

Es distinto el caso de la diagonal, que implica agregar un trabajo $i$ a la máquina 2 sabiendo que la máquina 1 termina con el elemento $i - 1$. En este caso, el trabajo que la máquina 2 había realizado antes de que le agreguemos el trabajo $i$ es desconocido. Debemos darnos un criterio entonces para calcularlo. El criterio adoptado es el siguiente: voy a asumir que el trabajo que realiza la máquina 2 antes que le agreguemos el trabajo $i$ es el que minimiza el costo de realizar los trabajos anteriores sumándole el trabajo i.

Nuestro algoritmo comienza llenando el primer valor de la diagonal (la posición [0,0] de la matriz, el primer cuadrado) con el valor de agregar el primer trabajo (el único valor posible para el primer trabajo). A partir de ahí, va a empezar a iterar fila por fila cada una de las filas de la matriz arrancando desde la primera. Teniendo el valor de la diagonal correspondiente a la fila que está recorriendo ya completado (recordemos que la primera casilla de la diagonal se completa antes de entrar al ciclo), el algoritmo completa el resto de la fila poniendo en la columna $j$ el valor de agregarle el trabajo $j$ a una máquina que realizó antes el trabajo $j - 1$ (sabemos que estos valores son los correctos por lo explicado en párrafos anteriores). Luego de completar la fila $i$ entera, el algoritmo completa la primer casilla de la fila $i + 1$ (la de la diagonal) para que al iterar la siguiente fila el algoritmo tenga un valor con el que pueda arrancar. Para completar esta casilla, debe encontrar el costo mínimo para $i$ trabajos sumandole el valor de agregar el trabajo $i + 1$ a la máquina que no termina con el trabajo $i$. Las posibilidades son por lo tanto, que la otra máquina termine con cualquiera de los $i - 1$ trabajos, o que directamente, no tenga aún ningún trabajo asignado. En total, son $i$ posibilidades distintas. El algoritmo tiene que chequearlas todas y encontrar la de menor costo. Para hacer esto, cuenta en la columna $i$ con todos los costos posibles de los trabajos para los distintos valores que pueda tomar la máquina que no termina con el trabajo $i$. Compara entonces cada uno de los valores de estas columnas entre sí sumándoles el costo de agregar el trabajo $i + 1$ luego del trabajo anterior correspondiente. En la figura 2 puede observarse un ejemplo para $i = 3$. En este caso, las casillas marrones son las que se llenan primero a partir del valor de la casilla [i, i]. Luego se llena la casilla $i + 1$ a partir de comparar entre si las casillas marcadas con rojo.

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej1-2.png}}
\caption{Ejemplo de cómo itera el algoritmo sobre una fila para $i = 3$}
\label{fig:matriz2}
\end{figure}

A su vez, al completar cada una de estas casillas diagonales, guardamos en la posición $i + 1$ de un array el número de trabajo previo que ejecuto la máquina antes del trabajo $i + 1$. De esta manera podemos saber no solamente el costo mínimo total del orden óptimo de los trabajos sino también cómo es exactamente ese orden óptimo.

\subsection{Correctitud}

Queremos demostrar que nuestro algoritmo encuentra la distribución de los trabajos entre las máquinas de tal manera que sus costos sean mínimos y que devuelve luego esa distribución junto con el costo total.

\underline{Lema:} Para cada columna $i$ de la matriz que tenemos que completar en la fila $j$ se encuentra el costo mínimo de entre los distintos posibles ordenes tales que con $i + 1$ cantidad de trabajos, una de las máquinas termine con el trabajo $i + 1$ y la otra con el trabajo $j$.

\underline{Demostración:}

\textit{Caso base:} $i = 0$.

La primer casilla de la matriz está completada con el valor de agregar el primer trabajo a una máquina vacía. Esto es, con un trabajo, tengo el valor mínimo (el único valor) tal que con 1 sólo trabajo una de las máquinas termina con el trabajo 0 (o sea, ningún trabajo).

\textit{Paso inductivo:} $P(i) \Rightarrow P(i + 1)$

Asumimos que en la columna $i$ de la matriz, para todos los valores de $j$ con $j \leq i$ en la fila $j$ se encuentra el minimo costo de realizar los primeros $i + 1$ trabajos tal que una de las máquinas finalice con el trabajo $j$. Queremos demostrar que lo mismo vale para $i + 1$ y $j$ tal que $j \leq i + 1$. Tomamos dos casos:

\underline{Primer caso:} $j < i + 1$. Nuestro algoritmo lo que hace en este caso es sumar el costo de agregar el trabajo $i + 2$ como si se realizara luego del trabajo $i + 1$. Observamos que dado que $j < i + 1$, en particular $j \leq i$, podemos garantizar que en la columna $i$ la casilla correspondiente a la fila $j$ tiene un valor que representa el costo mínimo de procesar los trabajos de tal manera que una de las máquinas termine con el trabajo $j$ y la otra con el trabajo $i + 1$ por Hipótesis Inductiva (esto es necesariamente así dado que se procesaron $i + 1$ trabajos en orden. Si una de las máquinas termina con el trabajo $j$ con $j < i + 1$ entonces necesariamente la maquina faltante debe procesar el trabajo $i + 1$). Observamos que para cualquier orden de los trabajos $D_{j, i}$ tal que una de las máquinas termine con el trabajo $j$ y la otra con el trabajo $i + 1$, el costo del orden de los trabajos $D_{j, i + 1}$ es igual al costo de $D_{j, i}$ + $T_{i, i + 1}$ (el costo de agregar el trabajo $i + 2$ luego del trabajo $i + 1$). Como ese valor $T_{i, i + 1}$ es igual sea cual sea el $D_{j, i}$, la forma de minimizar la suma y encontrar el $D_{j, i + 1}$ mínimo, es utilizando para la suma el $D_{j, i}$ mínimo. Pero esto es justamente lo que nos garantiza la H.I., que vamos a calcular $D_{j, i + 1}$ a partir del $D_{j, i}$ que sea mínimo.

\underline{Segundo caso:} $j = i + 1$. En este caso, queremos obtener el costo mínimo de sumar a una máquina (supongamos la máquina 1 sin pérdida de generalidad) el trabajo $i + 2$ sabiendo que la otra máquina (máquina 2) realiza el trabajo $i + 1$. Observemos que existen exactamente $i$ posibilidades según cual haya sido el último trabajo que realizó la máquina 1. Asumamos que el último trabajo realizado por esta máquina fue el trabajo $k$ con $k \leq i$. Entonces, el costo del orden de los trabajos $D_{j, i + 1}$ con una máquina que realiza en último lugar el trabajo $j = i + 1$ y la otra el trabajo $i + 2$, sería igual que el costo de $D_{j, k - 1} + T_{k, i + 1}$ (sumarle al costo del orden donde una máquina termina con el trabajo $k$ y la otra con el trabajo $j = i + 1$ el costo de agregar el trabajo $i + 2$ después del trabajo $k$). Nuevamente, como en el caso anterior, una vez que conocemos k, el valor de $T_{k, i + 1}$ está fijo. Para minimizar el valor de $D_{j, i + 1}$ es necesario tomar el valor mínimo de $D_{j, k - 1}$ al hacer la suma. Ahora bien, sabemos que para cualquier $k$ con $k \leq i$, el valor mínimo de $D_{j, k - 1}$ (o mejor dicho, de $D_{i + 1, k - 1}$) se encuentra en la columna $i + 1$ (esto nos lo garantiza la H.I.). Pero falta encontrar el valor adecuado de $k$ tal que entre todos los $D_{j, k - 1}$ el valor sea el mínimo. Nuestro algoritmo garantiza encontrar el k correcto dado que prueba uno por uno el resultado de sumar $D_{j, k - 1} + T_{k, i + 1}$, $\forall k / k \leq i$ y se queda con el menor de todos.

Hemos demostrado entonces, que para cada columna $i$ de la matriz, en cada fija $j$ se encuentra el minimo costo de realizar los primeros $i + 1$ trabajos tal que una de las máquinas finalice con el trabajo $j$. En particular, si la cantidad de trabajos total es \texttt{cantTrabajos}, en cada fila $w$ de la columna \texttt{cantTrabajos - 1} vamos a poder encontrar el costo mínimo entre todos los órdenes tal que una de las máquinas termine con el trabajo $T_{cantTrabajos}$ y la otra con el trabajo $T_{w}$. Ante esta situación, para encontrar el costo menor de entre todas los valores que puede tomar $w$, nuestro algoritmo compara todos los costos de los ordenes $D_{w, cantTrabajos - 1}$ con $w \leq cantTrabajos - 1$. Esto garantiza, al recorrer el abanico completo de los costos de todos los $D_{w, cantTrabajos - 1}$ que encuentre el que tiene el costo menor.

Por lo demostrado anteriormente, observamos que existe un sólo caso en el que un trabajo $i$ se agrega en una máquina (supongamos la máquina 1) detrás de un trabajo que no es el $i - 1$ (que es el caso en el que el trabajo $i - 1$ es realizado por la máquina 2). Por lo tanto, para una cantidad de trabajos igual a \texttt{cantTrabajos}, podemos guardar en un arreglo de tamaño \texttt{cantTrabajos} en cada posición $i$ del arreglo cuál es el trabajo realizado antes que el trabajo $i$ para el único caso en que este trabajo no es el $i - 1$. Cuando seleccionamos el valor $w$ que hace que el costo de un orden $D_{w, cantTrabajos - 1}$ sea el mínimo, sabemos cuales son los trabajos finales de las dos máquinas. También podemos deducir que todos los valores entre $w$ y \texttt{cantTrabajos} están en la misma máquina que cantTrabajos. Luego, debemos observar cuál es el trabajo que realizó esa máquina antes de $w + 1$ (que no puede ser $w$ porque está en la otra máquina). Finalmente, repetimos esta operación para los nuevos últimos trabajos que realizó la máquina luego de descartar los trabajos que van desde $w + 1$ hasta \texttt{cantTrabajos}.

\subsection{Análisis de complejidad}\label{complejidad3}

\subsubsection{Pseudocódigo}

Sean $n$ la cantidad de trabajos para distribuir entre las dos máquinas, el pseudocódigo del algoritmo con su complejidad es el siguiente:

\begin{algorithm}

    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{ouput}
    \SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
    \SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

    \SetKwData{A}{A}
    \SetKwData{n}{n}

    \Input{Entero \texttt{cantTrabajos}, Matriz \texttt{matrizValores}}
    \Output{Lista de Enteros \texttt{Resultado}}
    %~ \BlankLine
    crear una matriz de \texttt{cantTrabajos} * \texttt{cantTrabajos} \Complejidad*[r]{\color{blue}$1$}
    poner en la casilla $[0, 0]$ de la matriz el primer valor de \texttt{matrizValores} coorespondiente al valor de agregar el primer trabajo a cualquier máquina vacía \Complejidad*[r]{\color{blue}$1$}
    \For(\Complejidad*[f]{\color{blue}$n$}){cada fila $i$ de la matriz} {
		\For(\Complejidad*[f]{\color{blue}$n$}){cada columna $j$ entre $i$ y \texttt{cantTrabajos}} {
			Poner el valor de la columna $j - 1$ en la columna $j$ sumándole el valor de agregar el trabajo $j$ luego del trabajo $j - 1$ \Complejidad*[r]{\color{blue}$1$}
		}
		aux $= \infty$ \Complejidad*[r]{\color{blue}$1$}
		\For(\Complejidad*[f]{\color{blue}$n$}){cada fila $k$ entre $0$ e $i$} {
			aux = min(aux, valor de $[k, i]$ (fila $k$ columna $i$)) \Complejidad*[r]{\color{blue}$1$}
			si aux cambió, me guardo el valor de k en $log_aux$ \Complejidad*[r]{\color{blue}$1$}
		}
		Le asigno a la posición $[i + 1, i + 1]$ de la matriz el valor de aux \Complejidad*[r]{\color{blue}$1$}
		En el array $log[i]$ le asigno el valor de $log_aux$ (el valor del trabajo anterior al $i + 1$) \Complejidad*[r]{\color{blue}$1$}
	}
    \caption{Ejercicio 1}
    \label{pseudocodigo1}
\end{algorithm}

\subsubsection{Análisis}

El algoritmo consta de un ciclo principal que itera sobre las $n$ filas. Dentro de este ciclo, podemos encontrar otros dos ciclos independientes entre sí. Para cada fila $i$, uno itera sobre las columnas que hay entre la columna $i$ y el final de la matriz, y el otro recorre las filas ya recorridas. En el peor de los casos, cada uno de estos dos ciclos itera $n$ veces. Por lo tanto, la complejidad total la podemos calcular de la siguiente manera:

\begin{center}
$O(n* (n+n)) \subset O(n*2n) \subset O(2n^2) \subset O(n^2)$
\end{center}

\subsection{Análisis de casos}

Caso 1) no hay tareas a resolver.

No hay nada que resolver.

\begin{verbatim}
INPUT:
0

OUTPUT:
*NULO*
\end{verbatim}

Caso 2) el costo de las tareas individualmente es siempre ascendente.

El resultado para instancias como la siguiente sigue un patrón intercalado. La siguiente tarea se encolará detrás de la lista opuesta a la que se agregó la tarea actual. Según como se va aumentando el incremento, el intercalado se va ``desfansando'' de una manera mas irregular.

\begin{verbatim}
INPUT: 
5
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

OUTPUT:
31 2 2 4
\end{verbatim}

Caso 3) el costo de las tareas individualmente es descendente.

En casos así, siempre es mas conveniente encolar la siguiente tarea detrás de la tarea actual. Por lo tanto, una lista siempre quedará vacía.

\begin{verbatim}
INPUT: 
5
15
14 13
12 11 10
9 8 7 6
5 4 3 2 1

OUTPUT:
45 0
\end{verbatim}

\subsection{Test de performance}

Recordando que la complejidad esperada es $O(n^2)$, graficamos los tiempos medidos al resolver instancias con costos aleatorios y cantidad de tareas entre 3 y 100 unidades. Las instancias aleatorias fueron creadas con un script hecho en Python. A su vez los tiempos fueron medidos con la librería de C \texttt{times.h}. Comparamos ambas curvas y observamos que la cota establecida es correcta a partir de instancias mayores a 30 tareas.

\begin{center}
	\includegraphics[scale=.7]{ej1-analisis-casos.png} \\
	Figura 3: Complejidad temporal para instancias de tamaño creciente
\end{center}

\subsection{Código Fuente}

Incluimos a continuación la función principal del código fuente de nuestro algoritmo:

\begin{verbatim}

list<int> ordenar_trabajos(int cantTrabajos, vector< vector<int> > matrizValores) {
    int aux;
    int k;
    int resultadoParcial[cantTrabajos][cantTrabajos];
    int log[cantTrabajos];
    resultadoParcial[0][0] = matrizValores[0][0];
      
    /* Acá llena la matriz */
    for(int i = 0; i < cantTrabajos - 1; i++) {
        /* Primero completa la fila que está recorriendo sumandole los trabajos
        uno atrás del otro */
        for(int a = i + 1; a < cantTrabajos; a++) {
            resultadoParcial[i][a] = resultadoParcial[i][a-1] + matrizValores[a][a];
        }
        /* Después completa la primera casilla de la fila siguiente 
        calculando los mínimos entre los valores de la columna i */
        aux = INF;
        for(int k = i; k >= 0; k--) {
            if(aux > (resultadoParcial[k][i] + matrizValores[i + 1][k])){
                aux = resultadoParcial[k][i] + matrizValores[i + 1][k];
                log[i + 1] = k;
            }                        
        }                        
        resultadoParcial[i + 1][i + 1] = aux;                    
    }

    /* Acá encuentra el valor mínimo entre la última columna de la matriz */
    aux = INF;
    int coordenada;
    int recorrer;
    int terminar;
    for(int j = 0; j < cantTrabajos; j++) {   
        if(aux > resultadoParcial[j][cantTrabajos - 1]){
            aux = resultadoParcial[j][cantTrabajos - 1];
            coordenada = j;
        }            
    }
    
    /* Acá reconstruye qué trabajo va en cada máquina */
    list<int> resultado;
    log[0] = -1;
    recorrer = coordenada;
    terminar = log[coordenada];
      
    while(recorrer != -1 && terminar != -1) {
        for(int c = recorrer; c > terminar; c--){
            resultado.push_front(c);
        }
        recorrer = log[terminar];
        terminar = log[recorrer];
    }

    resultado.push_front(resultado.size());
    resultado.push_front(aux);
    return resultado;
}
\end{verbatim}
